package AboutSort;

public class MergeSort {

    public static void mergeSort(int[] arr,int l,int r) {
        if(l == r) {
            return;
        }

        int m = (l + r) / 2;
        System.out.println("m的值为:"+m);
        mergeSort(arr,l,m);
        mergeSort(arr,m+1,r);

        merge(arr,l,m,r);
    }


    //并
    public static void merge(int[] arr,int l,int m,int r) {
        //将数组分为两个数组
        int[] a = new int[m-l+1];
        int[] b = new int[r-m];

        int temp = l;
        for(int i = 0 ; i < a.length;  i++) {
            a[i] = arr[temp];
            temp++;
        }

        temp = m+1;

        for(int j = 0 ; j < b.length ; j++) {
            b[j] = arr[temp];
            temp++;
        }

        //merge two arrays
        int lenA = a.length;
        int lenB = b.length;
        int index = 0;
        System.out.println("lenA:"+lenA+",lenB:"+lenB);
        int indexA = 0;
        int indexB = 0;
        int[] c = new int[lenA + lenB];

        while(indexA < lenA && indexB < lenB) {
            if(a[indexA] < b[indexB]) {
                c[index] = a[indexA];
                indexA++;
                index++;
            } else {
                c[index] = b[indexB];
                indexB++;
                index++;
            }
        }

        while(indexA < lenA) {
            c[index] = a[indexA];
            indexA++;
            index++;
        }

        while(indexB < lenB) {
            c[index] = b[indexB];
            indexB++;
            index++;
        }

        temp = l;

        for(int k = 0 ; k < c.length ; k++) {
            arr[temp] = c[k];
            temp++;
        }


    }

    public static void main(String[] args) {

        int[] a = {9,10,11,12,6,7,8};

        mergeSort(a,0,6);

        System.out.println("归并排序后的结果为:");
        for(int temp : a) {
            System.out.print(temp + " ");
        }
    }
}
